import java.util.Random;

//双路快速排序
public class QuickSort2 {
    private QuickSort2() {
    }

    public static <E extends Comparable<E>> void sort2ways(E[] arr) {
        Random rnd = new Random();
        sort2ways(arr, 0, arr.length - 1, rnd);
    }

    public static <E extends Comparable<E>> void sort2ways(E[] arr, int l, int r, Random rnd) {
        if (l >= r) {
            return;
        }
        int partition = partition2(arr, l, r, rnd);
        sort2ways(arr, l, partition - 1, rnd);
        sort2ways(arr, partition + 1, r, rnd);
    }

    //分区 首先需要知道分区后标定点左边的数要比标定点小，标定点右边的数要比标定点大
    public static <E extends Comparable<E>> int partition2(E[] arr, int l, int r, Random rnd) {
        //arr[l+1---j] <=v   arr[j+1---i] >=v
        //作为标定点
        int p = l + rnd.nextInt(r - l + 1);
        swap(arr, l, p);
        int i = l + 1;
        int j = r;
        while (true) {
            //只要前指针小于后指针，并且前指针指向的值小于l，则前指针递增
            while (i <= j && arr[i].compareTo(arr[l]) < 0) {
                i++;
            }
            //只要前指针小于后指针，并且后指针指向的值大于l，则后指针递减
            while (j >= i && arr[j].compareTo(arr[l]) > 0) {
                j--;
            }
            //如果i大于等于j了，就跳出循环
            if (i >= j) {
                break;
            }
            //交换前后指针指向的值的位置
            swap(arr, i, j);
            //双指针分别前进
            i++;
            j--;
        }
        //最后交换l和j的位置
        swap(arr, l, j);
        return j;
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
